home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / bigkey.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  17KB  |  672 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bigkey.c    5.5 (Berkeley) 3/12/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. /******************************************************************************
  42.  
  43. PACKAGE: hash
  44.  
  45. DESCRIPTION:
  46.     Big key/data handling for the hashing package.
  47.  
  48. ROUTINES:
  49.     External
  50.     __big_keydata
  51.     __big_split
  52.     __big_insert
  53.     __big_return
  54.     __big_delete
  55.     __find_last_page
  56.     Internal
  57.     collect_key
  58.     collect_data
  59. ******************************************************************************/
  60. /* Includes */
  61. #define KERNEL
  62. #include "ixnet.h"
  63. #include <sys/param.h>
  64. #include <errno.h>
  65. #include <db.h>
  66. #include <stdio.h>
  67. #include <stdlib.h>
  68. #include <string.h>
  69. #include "hash.h"
  70. #include "page.h"
  71. #include "utils.h"
  72.  
  73. #define assert(x) \
  74. { \
  75.     if(!x) {\
  76.     fprintf(stderr,"assertion failed on line %d, in file %s\n",__LINE__,__FILE__); \
  77.     exit(1);\
  78.     }\
  79. }
  80.  
  81. /* Externals */
  82. /* buf.c */
  83. extern BUFHEAD *__get_buf();
  84.  
  85. /* dynahash.c */
  86. extern    u_int call_hash();
  87.  
  88. /* My internals */
  89. static int collect_key();
  90. static int collect_data();
  91.  
  92. #ifdef HASH_STATISTICS
  93. extern long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  94. #endif
  95. /*
  96. Big_insert
  97.  
  98. You need to do an insert and the key/data pair is too big
  99. 0 ==> OK
  100. -1 ==> ERROR
  101. */
  102. extern int
  103. __big_insert ( bufp, key, val )
  104. BUFHEAD *bufp;
  105. DBT    *key, *val;
  106. {
  107.     char    *cp = bufp->page;    /* Character pointer of p */
  108.     register u_short    *p = (u_short *)cp;
  109.     char    *key_data, *val_data;
  110.     int     key_size, val_size;
  111.     int     n;
  112.     u_short    space, move_bytes, off;
  113.  
  114.     key_data = (char *)key->data;
  115.     key_size = key->size;
  116.     val_data = (char *)val->data;
  117.     val_size = val->size;
  118.  
  119.     /* First move the Key */
  120.     for ( space = FREESPACE(p) - BIGOVERHEAD;
  121.       key_size;
  122.       space = FREESPACE(p) - BIGOVERHEAD ) {
  123.     move_bytes = MIN(space, key_size);
  124.     off = OFFSET(p) - move_bytes;
  125.     bcopy (key_data, cp+off, move_bytes );
  126.     key_size -= move_bytes;
  127.     key_data += move_bytes;
  128.     n = p[0];
  129.     p[++n] = off;
  130.     p[0] = ++n;
  131.     FREESPACE(p) = off - PAGE_META(n);
  132.     OFFSET(p) = off;
  133.     p[n] = PARTIAL_KEY;
  134.     bufp = __add_ovflpage(bufp);
  135.     if ( !bufp ) {
  136.         return(-1);
  137.     }
  138.     n = p[0];
  139.     if ( !key_size ) {
  140.         if ( FREESPACE(p) ) {
  141.         move_bytes = MIN (FREESPACE(p), val_size);
  142.         off = OFFSET(p) - move_bytes;
  143.         p[n] = off;
  144.         bcopy ( val_data, cp + off, move_bytes );
  145.         val_data += move_bytes;
  146.         val_size -= move_bytes;
  147.         p[n-2] = FULL_KEY_DATA;
  148.         FREESPACE(p) = FREESPACE(p) - move_bytes;
  149.         OFFSET(p) = off;
  150.         }
  151.         else p[n-2] = FULL_KEY;
  152.     }
  153.     p = (u_short *)bufp->page;
  154.     cp = bufp->page;
  155.     bufp->flags |= BUF_MOD;
  156.     }
  157.  
  158.     /* Now move the data */
  159.     for ( space = FREESPACE(p) - BIGOVERHEAD;
  160.       val_size;
  161.       space = FREESPACE(p) - BIGOVERHEAD ) {
  162.     move_bytes = MIN(space, val_size);
  163.     /*
  164.         Here's the hack to make sure that if the data ends
  165.         on the same page as the key ends, FREESPACE is
  166.         at least one
  167.     */
  168.     if ( space == val_size && val_size == val->size ) {
  169.         move_bytes--;
  170.     }
  171.     off = OFFSET(p) - move_bytes;
  172.     bcopy (val_data, cp+off, move_bytes );
  173.     val_size -= move_bytes;
  174.     val_data += move_bytes;
  175.     n = p[0];
  176.     p[++n] = off;
  177.     p[0] = ++n;
  178.     FREESPACE(p) = off - PAGE_META(n);
  179.     OFFSET(p) = off;
  180.     if ( val_size ) {
  181.         p[n] = FULL_KEY;
  182.         bufp = __add_ovflpage (bufp);
  183.         if ( !bufp ) {
  184.         return(-1);
  185.         }
  186.         cp = bufp->page;
  187.         p = (u_short *)cp;
  188.     } else {
  189.         p[n] = FULL_KEY_DATA;
  190.     }
  191.     bufp->flags |= BUF_MOD;
  192.     }
  193.     return(0);
  194. }
  195.  
  196. /*
  197.     Called when bufp's page  contains a partial key (index should be 1)
  198.  
  199.     All pages in the big key/data pair except bufp are freed.  We cannot
  200.     free bufp because the page pointing to it is lost and we can't
  201.     get rid of its pointer.
  202.  
  203.     Returns 0 => OK
  204.         -1 => ERROR
  205. */
  206. extern int
  207. __big_delete (bufp, ndx)
  208. BUFHEAD *bufp;
  209. int    ndx;
  210. {
  211.     register    BUFHEAD     *rbufp = bufp;
  212.     register    BUFHEAD     *last_bfp = NULL;
  213.     u_short *bp = (u_short *)bufp->page;
  214.     u_short pageno = 0;
  215.     int    key_done = 0;
  216.     int    n;
  217.  
  218.     while (!key_done || (bp[2] != FULL_KEY_DATA)) {
  219.         if ( bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA ) key_done = 1;
  220.  
  221.         /*
  222.         If there is freespace left on a FULL_KEY_DATA page,
  223.         then the data is short and fits entirely on this
  224.         page, and this is the last page.
  225.         */
  226.         if ( bp[2] == FULL_KEY_DATA && FREESPACE(bp) ) break;
  227.         pageno = bp[bp[0]-1];
  228.         rbufp->flags |= BUF_MOD;
  229.         rbufp = __get_buf ( pageno, rbufp, 0 );
  230.         if ( last_bfp ) __free_ovflpage(last_bfp);
  231.         last_bfp = rbufp;
  232.         if ( !rbufp ) return(-1);                   /* Error */
  233.         bp = (u_short *)rbufp->page;
  234.     }
  235.  
  236.     /*
  237.         If we get here then rbufp points to the last page of
  238.         the big key/data pair.  Bufp points to the first
  239.         one -- it should now be empty pointing to the next
  240.         page after this pair.  Can't free it because we don't
  241.         have the page pointing to it.
  242.     */
  243.  
  244.     /* This is information from the last page of the pair */
  245.     n = bp[0];
  246.     pageno = bp[n-1];
  247.  
  248.     /* Now, bp is the first page of the pair */
  249.     bp = (u_short *)bufp->page;
  250.     if ( n > 2 ) {
  251.         /* There is an overflow page */
  252.         bp[1] = pageno;
  253.         bp[2] = OVFLPAGE;
  254.         bufp->ovfl = rbufp->ovfl;
  255.     } else {
  256.         /* This is the last page */
  257.         bufp->ovfl = NULL;
  258.     }
  259.     n -= 2;
  260.     bp[0] = n;
  261.     FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
  262.     OFFSET(bp) = hashp->BSIZE - 1;
  263.  
  264.     bufp->flags |= BUF_MOD;
  265.     if ( rbufp ) __free_ovflpage(rbufp);
  266.     if ( last_bfp != rbufp ) __free_ovflpage(last_bfp);
  267.  
  268.     hashp->NKEYS--;
  269.     return(0);
  270. }
  271.  
  272. /*
  273.     0 = key not found
  274.     -1 = get next overflow page
  275.     -2 means key not found and this is big key/data
  276.     -3 error
  277. */
  278. extern int
  279. __find_bigpair(bufp, ndx, key, size )
  280. BUFHEAD *bufp;
  281. int    ndx;
  282. char    *key;
  283. int    size;
  284. {
  285.     register    u_short *bp = (u_short *)bufp->page;
  286.     register    char    *p = bufp->page;
  287.     int     ksize = size;
  288.     char    *kkey = key;
  289.     u_short    bytes;
  290.  
  291.  
  292.     for ( bytes = hashp->BSIZE - bp[ndx];
  293.       bytes <= size && bp[ndx+1] == PARTIAL_KEY;
  294.       bytes = hashp->BSIZE - bp[ndx] ) {
  295.  
  296.     if ( bcmp ( p+bp[ndx], kkey, bytes ))return(-2);
  297.     kkey += bytes;
  298.     ksize -= bytes;
  299.     bufp = __get_buf ( bp[ndx+2], bufp, 0 );
  300.     if ( !bufp ) {
  301.         return(-3);
  302.     }
  303.     p = bufp->page;
  304.     bp = (u_short *)p;
  305.     ndx = 1;
  306.     }
  307.  
  308.     if ( (bytes != ksize) || bcmp ( p+bp[ndx], kkey, bytes )) {
  309. #ifdef HASH_STATISTICS
  310.     hash_collisions++;
  311. #endif
  312.     return(-2);
  313.     }
  314.     else return (ndx);
  315. }
  316.  
  317.  
  318. /*
  319.     Given the buffer pointer of the first overflow page of a big pair,
  320.     find the end of the big pair
  321.  
  322.     This will set bpp to the buffer header of the last page of the big pair.
  323.     It will return the pageno of the overflow page following the last page of
  324.     the pair; 0 if there isn't any (i.e. big pair is the last key in the
  325.     bucket)
  326. */
  327. extern u_short
  328. __find_last_page ( bpp )
  329. BUFHEAD **bpp;
  330. {
  331.     int    n;
  332.     u_short pageno;
  333.     BUFHEAD *bufp = *bpp;
  334.     u_short *bp = (u_short *)bufp->page;
  335.  
  336.     while ( 1 ) {
  337.         n = bp[0];
  338.  
  339.         /*
  340.         This is the last page if:
  341.             the tag is FULL_KEY_DATA and either
  342.                 only 2 entries
  343.                 OVFLPAGE marker is explicit
  344.                 there is freespace on the page
  345.         */
  346.         if ( bp[2] == FULL_KEY_DATA &&
  347.          ((n == 2) ||  (bp[n] == OVFLPAGE) || (FREESPACE(bp)) ) ) break;
  348.  
  349.         pageno = bp[n-1];
  350.         bufp = __get_buf ( pageno, bufp, 0 );
  351.         if ( !bufp ) return (0);            /* Need to indicate an error! */
  352.         bp = (u_short *)bufp->page;
  353.     }
  354.  
  355.     *bpp = bufp;
  356.     if ( bp[0] > 2 ) return ( bp[3] );
  357.     else return(0);
  358. }
  359.  
  360.  
  361. /*
  362.     Return the data for the key/data pair
  363.     that begins on this page at this index
  364.     (index should always be 1)
  365. */
  366. extern int
  367. __big_return ( bufp, ndx, val, set_current )
  368. BUFHEAD *bufp;
  369. int    ndx;
  370. DBT    *val;
  371. int    set_current;
  372. {
  373.     BUFHEAD    *save_p;
  374.     u_short    save_addr;
  375.     u_short    *bp = (u_short *)bufp->page;
  376.     u_short    off, len;
  377.     char    *tp;
  378.  
  379.     while ( bp[ndx+1] == PARTIAL_KEY ) {
  380.     bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  381.     if ( !bufp ) return(-1);
  382.     bp = (u_short *)bufp->page;
  383.     ndx = 1;
  384.     }
  385.  
  386.     if ( bp[ndx+1] == FULL_KEY ) {
  387.     bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  388.     if ( !bufp ) return(-1);
  389.     bp = (u_short *)bufp->page;
  390.     save_p = bufp;
  391.     save_addr = save_p->addr;
  392.     off = bp[1];
  393.     len = 0;
  394.     } else if (!FREESPACE(bp)) {
  395.     /*
  396.         This is a hack.  We can't distinguish between
  397.         FULL_KEY_DATA that contains complete data or
  398.         incomplete data, so we require that if the
  399.         data  is complete, there is at least 1 byte
  400.         of free space left.
  401.     */
  402.     off = bp[bp[0]];
  403.     len = bp[1] - off;
  404.     save_p = bufp;
  405.     save_addr = bufp->addr;
  406.     bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  407.     if ( !bufp ) return(-1);
  408.     bp = (u_short *)bufp->page;
  409.     } else {
  410.     /* The data is all on one page */
  411.     tp = (char *)bp;
  412.     off = bp[bp[0]];
  413.     val->data = (u_char *)tp + off;
  414.     val->size = bp[1] - off;
  415.     if ( set_current ) {
  416.         if ( bp[0] == 2 ) {         /* No more buckets in chain */
  417.         hashp->cpage = NULL;
  418.         hashp->cbucket++;
  419.         hashp->cndx=1;
  420.         } else  {
  421.         hashp->cpage = __get_buf ( bp[bp[0]-1], bufp, 0 );
  422.         if ( !hashp->cpage )return(-1);
  423.         hashp->cndx = 1;
  424.         if ( !((u_short *)hashp->cpage->page)[0] ) {
  425.             hashp->cbucket++;
  426.             hashp->cpage = NULL;
  427.         }
  428.         }
  429.     }
  430.     return(0);
  431.     }
  432.  
  433.     val->size = collect_data ( bufp, len, set_current );
  434.     if ( val->size == -1 ) {
  435.     return(-1);
  436.     }
  437.     if ( save_p->addr != save_addr ) {
  438.     /* We are pretty short on buffers */
  439.     errno = EINVAL;     /* OUT OF BUFFERS */
  440.     return(-1);
  441.     }
  442.     bcopy ( (save_p->page)+off, hashp->tmp_buf, len );
  443.     val->data = (u_char *)hashp->tmp_buf;
  444.     return(0);
  445. }
  446.  
  447. /*
  448.     Count how big the total datasize is by
  449.     recursing through the pages.  Then allocate
  450.     a buffer and copy the data as you recurse up.
  451. */
  452. static int
  453. collect_data ( bufp, len, set )
  454. BUFHEAD *bufp;
  455. int    len;
  456. int    set;
  457. {
  458.     register    char    *p = bufp->page;
  459.     register    u_short *bp = (u_short *)p;
  460.     u_short    save_addr;
  461.     int mylen, totlen;
  462.     BUFHEAD    *xbp;
  463.  
  464.     mylen = hashp->BSIZE - bp[1];
  465.     save_addr = bufp->addr;
  466.  
  467.     if ( bp[2] == FULL_KEY_DATA ) {     /* End of Data */
  468.     totlen = len + mylen;
  469.     if ( hashp->tmp_buf ) free (hashp->tmp_buf);
  470.     hashp->tmp_buf = (char *)malloc ( totlen );
  471.     if ( !hashp->tmp_buf ) {
  472.         return(-1);
  473.     }
  474.     if ( set ) {
  475.         hashp->cndx = 1;
  476.         if ( bp[0] == 2 ) {         /* No more buckets in chain */
  477.         hashp->cpage = NULL;
  478.         hashp->cbucket++;
  479.         } else  {
  480.         hashp->cpage = __get_buf ( bp[bp[0]-1], bufp, 0 );
  481.         if (!hashp->cpage) {
  482.             return(-1);
  483.         } else if ( !((u_short *)hashp->cpage->page)[0] ) {
  484.             hashp->cbucket++;
  485.             hashp->cpage = NULL;
  486.         }
  487.         }
  488.     }
  489.     } else {
  490.     xbp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  491.     if ( !xbp || ((totlen = collect_data ( xbp, len + mylen, set )) < 1) ) {
  492.         return(-1);
  493.     }
  494.     }
  495.     if ( bufp->addr != save_addr ) {
  496.     errno = EINVAL;     /* Out of buffers */
  497.     return(-1);
  498.     }
  499.     bcopy ( (bufp->page) + bp[1], &hashp->tmp_buf[len], mylen );
  500.     return ( totlen );
  501. }
  502.  
  503. /*
  504.     Fill in the key and data
  505.     for this big pair
  506. */
  507. extern int
  508. __big_keydata ( bufp, ndx, key, val, set )
  509. BUFHEAD *bufp;
  510. int    ndx;
  511. DBT    *key, *val;
  512. int    set;
  513. {
  514.     key->size = collect_key ( bufp, 0, val, set );
  515.     if ( key->size == -1 ) {
  516.     return (-1);
  517.     }
  518.     key->data = (u_char *)hashp->tmp_key;
  519.     return(0);
  520. }
  521.  
  522. /*
  523.     Count how big the total key size is by
  524.     recursing through the pages.  Then collect
  525.     the data, allocate a buffer and copy the key as
  526.     you recurse up.
  527. */
  528. static int
  529. collect_key ( bufp, len, val, set )
  530. BUFHEAD *bufp;
  531. int    len;
  532. DBT    *val;
  533. int    set;
  534. {
  535.     char    *p = bufp->page;
  536.     u_short    *bp = (u_short *)p;
  537.     u_short    save_addr;
  538.     int mylen, totlen;
  539.     BUFHEAD    *xbp;
  540.  
  541.     mylen = hashp->BSIZE - bp[1];
  542.  
  543.     save_addr = bufp->addr;
  544.     totlen = len + mylen;
  545.     if ( bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA ) {/* End of Key */
  546.     if ( hashp->tmp_key ) free (hashp->tmp_key);
  547.     hashp->tmp_key = (char *)malloc ( totlen );
  548.     if ( !hashp->tmp_key ) {
  549.         return(-1);
  550.     }
  551.     __big_return ( bufp, 1, val, set );
  552.     } else {
  553.     xbp = __get_buf (bp[bp[0]-1], bufp, 0);
  554.     if ( !xbp || ((totlen = collect_key (xbp, totlen, val, set)) < 1 ) ) {
  555.         return(-1);
  556.     }
  557.     }
  558.     if ( bufp->addr != save_addr ) {
  559.     errno = EINVAL;     /* MIS -- OUT OF BUFFERS */
  560.     return (-1);
  561.     }
  562.     bcopy ( (bufp->page) + bp[1], &hashp->tmp_key[len], mylen );
  563.     return ( totlen );
  564. }
  565.  
  566.  
  567. extern u_int __call_hash();
  568.  
  569. /*
  570.     return 0 => OK
  571.        -1 => error
  572. */
  573. extern int
  574. __big_split ( op, np, big_keyp, addr, obucket, ret )
  575. BUFHEAD *op;        /* Pointer to where to put keys that go in old bucket */
  576. BUFHEAD *np;        /* Pointer to new bucket page */
  577. BUFHEAD *big_keyp;    /* Pointer to first page containing the big key/data */
  578. u_short addr;        /* Address of big_keyp */
  579. u_int    obucket;    /* Old Bucket */
  580. SPLIT_RETURN    *ret;
  581. {
  582.     register    BUFHEAD *tmpp;
  583.     register    u_short     *tp;
  584.     BUFHEAD    *bp = big_keyp;
  585.     u_short    off, free_space;
  586.     u_short    n;
  587.  
  588.     DBT     key, val;
  589.  
  590.     u_int    change;
  591.  
  592.     /* Now figure out where the big key/data goes */
  593.     if (__big_keydata ( big_keyp, 1, &key, &val, 0 )) {
  594.     return(-1);
  595.     }
  596.     change = (__call_hash ( key.data, key.size ) != obucket );
  597.  
  598.     ret->next_addr = __find_last_page ( &big_keyp );
  599.     if (ret->next_addr) {
  600.     if (!(ret->nextp = __get_buf ( ret->next_addr, big_keyp, 0 ))) {
  601.         return(-1);;
  602.     }
  603.     } else {
  604.     ret->nextp = NULL;
  605.     }
  606.  
  607.     /* Now make one of np/op point to the big key/data pair */
  608.  
  609.     assert(np->ovfl == NULL);
  610.  
  611.     if ( change ) tmpp = np;
  612.     else tmpp = op;
  613.  
  614.     tmpp->flags |= BUF_MOD;
  615. #ifdef DEBUG1
  616.     fprintf ( stderr, "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
  617.         (tmpp->ovfl?tmpp->ovfl->addr:0),
  618.         (bp?bp->addr:0) );
  619. #endif
  620.     tmpp->ovfl = bp;        /* one of op/np point to big_keyp */
  621.     tp = (u_short *)tmpp->page;
  622.     assert ( FREESPACE(tp) >= OVFLSIZE);
  623.     n = tp[0];
  624.     off = OFFSET(tp);
  625.     free_space = FREESPACE(tp);
  626.     tp[++n] = addr;
  627.     tp[++n] = OVFLPAGE;
  628.     tp[0] = n;
  629.     OFFSET(tp) = off;
  630.     FREESPACE(tp) = free_space - OVFLSIZE;
  631.  
  632.     /*
  633.     Finally, set the new and old return values.
  634.     BIG_KEYP contains a pointer to the last page of the big key_data pair.
  635.     Make sure that big_keyp has no following page (2 elements) or create
  636.     an empty following page.
  637.     */
  638.  
  639.     ret->newp = np;
  640.     ret->oldp = op;
  641.  
  642.     tp = (u_short *)big_keyp->page;
  643.     big_keyp->flags |= BUF_MOD;
  644.     if ( tp[0] > 2 ) {
  645.     /*
  646.         There may be either one or two offsets on this page
  647.         If there is one, then the overflow page is linked on
  648.         normally and tp[4] is OVFLPAGE.  If there are two, tp[4]
  649.         contains the second offset and needs to get stuffed in
  650.         after the next overflow page is added
  651.     */
  652.     n = tp[4];
  653.     free_space = FREESPACE(tp);
  654.     off = OFFSET(tp);
  655.     tp[0] -= 2;
  656.     FREESPACE(tp) = free_space + OVFLSIZE;
  657.     OFFSET(tp) = off;
  658.     tmpp = __add_ovflpage ( big_keyp );
  659.     if ( !tmpp ) {
  660.         return(-1);
  661.     }
  662.     tp[4] = n;
  663.     } else {
  664.     tmpp = big_keyp;
  665.     }
  666.  
  667.     if ( change ) ret->newp = tmpp;
  668.     else ret->oldp = tmpp;
  669.  
  670.     return(0);
  671. }
  672.